package solutions.leetcode.hard;

import solutions.lib.BaseSolution;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/count-number-of-special-subsequences/">1955. 统计特殊子序列的数目</a>
 */
public class Solution1955 extends BaseSolution {

    public int countSpecialSubsequences(int[] nums) {
        int[] rst = new int[3];
        int mod = 1000000007;
        for (int v : nums) {
            rst[v] = (rst[v] * 2) % mod + (v == 0 ? 1 : rst[v - 1]);
            rst[v] %= mod;
        }
        return rst[2];
    }

    public static void main(String[] args) {
        Solution1955 solution = new Solution1955();
    }
}